/*
 * @lc app=leetcode.cn id=121 lang=java
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
class Solution {
    public int maxProfit(int[] prices) {
        int[] min_prices=new int[prices.length],
        max_price=new int[prices.length];
        int res=0;
        min_prices[0]=prices[0];
        max_price[prices.length-1]=prices[prices.length-1];
        for (int i = 1; i < max_price.length; i++) {
            min_prices[i]=Math.min(prices[i], min_prices[i-1]);
        }
        for (int i = max_price.length-2; i >=0; i--) {
            max_price[i]=Math.max(prices[i], max_price[i+1]);
        }
        for (int i = 0; i < max_price.length; i++) {
            res=Math.max(res, max_price[i]-min_prices[i]);
            
        }
        return res;

    }
}
// @lc code=end

